动态规划

二维数组初始化问题

dp = [[0] * (j) for _ in range(i)]

Edit Distance

dp[i][j]代表 word1[:i]和word2[:j]的编辑距离

查找最长的

Longest Palindromic Substring

dp[i][j]代表s[i:j+1]是回文串

Partition Equal Subset Sum

就是背包中可以填满一半。

变量有：用了多少位、和为一半

所以dp[i][j]代表用了前i位，和可以为j

Longest Valid Parentheses

(()))

最长合法字符串

涉及（和）都考虑用stack，stack可以记录每一个(和)的信息

WordBreak

LeetCode 提供Lee Leet Code，是否可以拆分

不会嵌套，其实就应该用单个dp

dp[i] 代表0:i

Maximum Product Subarray

解法一二维DP，dp[i][j]为max(dp[i+1][j]*nums[i],dp[i][j-1]*nums[j])，但是内存会超

考虑乘积的性质！

最大正数要么是之前的最大正数*正数和他自己，或者是最前的最小负数乘以负数。

最小负数要么是之前的最小负数乘以正数，要么是最大正数乘以负数